1. Field of the Invention
The present invention relates generally to computer-aided design of vehicles and, more specifically, to a method of real-time collision detection between solid geometric models in the design of a vehicle.
2. Description of the Related Art
Vehicle design, and in particular the design of an automotive vehicle, has advanced to a state in which computer aided design techniques are frequently incorporated in the development of a new vehicle, or redesign of an existing vehicle. At the same time, enhanced visualization software tools have been developed that allow for interactive display and evaluation of large models, including models developed using computer-aided design. In the field of vehicle design, the use of both computer-aided design and visualization techniques is especially beneficial in designing, packaging and assembling the various systems incorporated within the vehicle, to maximize the design and functional capabilities of these vehicles. Advantageously, potential vehicle system designs can be considered in a timely and cost-effective manner by analyzing a digital representation of a proposed design, versus preparing an actual vehicle model.
Various aspects of the design task for a vehicle include detecting interferences between components, evaluating assembly processes, and understanding vehicle ergonomics. Recently, these types of design tasks have been accomplished using tools such as virtual reality simulations.
A user-held interface device, such as a haptic interface, serves as a tactical interface between the user and the virtual world. The haptic interface allows the computing of reaction forces as a result of touching or pushing a virtual object and is a physical device that delivers the computed force to the user through end effectors. An example of such a haptic interface is disclosed in commonly assigned U.S. Pat. No. 5,694,013 to Stewart, et al., entitled “Force Feedback Haptic Interface for a Three-Dimensional CAD Surface,” the disclosure of which is incorporated by reference. Advantageously, the haptic device reproduces at a high rate of speed the sensation of freely moving an object within a constrained environment by determining the forces exchanged between the interacting geometries.
Collision detection is one technique used in conjunction with visualization tools to detect if and by how much two objects interpenetrate. More recently, there is a need for software tools that not only detect penetration, but also calculate the dynamic motion generated by the collisions between objects to compute reaction force by determining whether, and by how much, two objects interpenetrate. This process is referred to as collision rendering. Advantageously, collision rendering is applied in the simulation of dynamic models, that may be moving in response to internal and external forces. Collision rendering is also applicable to the design process to determine how an object moves within a constrained environment, such as the installation of an engine within the engine compartment of a vehicle. A disadvantage of collision rendering for a model as complex as a vehicle is that it is a mathematically complex problem and finding a solution in a predetermined time frame requires some approximations.
Various collision detection methods have been utilized in the past. One method involves a volumetric representation that divides a space into small eight-sided units, called voxels. Each voxel is assigned a value of zero if part of free space, or one if part of the object. The set of all voxels is called a voxmap. A collision is determined by computing the discrete position of a point in space in the voxmap and checking if the corresponding element is zero, representing no collision, or one, signaling a collision. While this method works well for simple systems, it is less accurate for more complex models, since the size of the individual voxel determines the accuracy of the geometric representation, and significant amounts of computer memory are required for complex models. Also, it is difficult to accurately prepare a voxmap from a model as complex as a CAD model of a vehicle, or convert a modified voxmap back into a CAD model.
Another method of collision detection includes creating a mesh model of the CAD model, which is a collection of polygons describing the surface of the CAD model. While this method works well, the search for a polygon colliding with the haptic device is more time consuming than the voxel method. Also, unless the CAD model is already in a mesh format, the geometry represented by a NURBS format, or other free form representation, has to be translated into a mesh. A disadvantage is a decrease in model fidelity and topology.
Still another method of collision detection includes a tracking algorithm to detect collisions with a free form surface. The tracking algorithm determines a tracking point on the surface of the CAD model using a numerical approximation starting from the closest point calculated during a previous iteration. Thus, once an initial point is found, the motion of a cursor can be tracked over the surface. Only the parametric domain and trim boundaries limit the tracking motion. While tracking algorithms work well for collision detection, it can be difficult and time consuming to find an initial starting point. Also, certain geometric features of a NURBS surface, such as ridges and cusps formed by points and knots need to be considered separately from the other NURBS surfaces of the CAD model. Traditionally, the closest point to a polygonal mesh is found by representing the mesh as an unconnected group of triangles. A map, such as a Voronoi map is used to assign the elements of the polygonal soup to different regions of the map, so that coherence can be exploited to check the distance to only those polygons belonging to regions that neighbor the current location of the potentially colliding point. However, this technique does not take advantage of connectivity between triangles by assuming the mesh represents a manifold and each triangle will have neighboring triangles, and each vertex a set of connected polygons.
Another example of a collision detection method is disclosed in co-pending patent application U.S. Ser. No. 09/686,601, the disclosure of which is hereby incorporated by reference. This method of collision detection is for a point-to-surface collision based on a tessellated mesh. While this method works well, its application is limited to the interaction between a point and a surface.
Thus, there is a need in the art for an efficient method of real-time collision detection between a solid moving object represented as a point cloud and a tessellated mesh of a solid, stationary object, and provides force feedback to a user regarding the collision.